package com.guet.DataStructures.linkedlist;

/**
 * @author MicahYin
 * @date 2020/10/27 11:07
 * java 实现双向链表
 */
public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode2 node1 = new HeroNode2(1,"刘备","刘玄德");
        HeroNode2 node2 = new HeroNode2(2,"关羽","关云长");
        HeroNode2 node3 = new HeroNode2(3,"张飞","张翼德");
        HeroNode2 node4 = new HeroNode2(4,"赵云","赵子龙");

        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();

        //按顺序添加节点
        doubleLinkedList.addByOrder(node1);
        doubleLinkedList.addByOrder(node3);
        doubleLinkedList.addByOrder(node4);
        doubleLinkedList.addByOrder(node2);
        doubleLinkedList.list();
        System.out.println("--------------");
        //修改节点
        HeroNode2 node5 = new HeroNode2(4,"诸葛亮","孔明");
        doubleLinkedList.update(node5);
        doubleLinkedList.list();
        System.out.println("--------------");
        //删除节点
        doubleLinkedList.del(4);
        doubleLinkedList.list();
    }
}
class DoubleLinkedList{
    //初始化头结点----头结点很关键，不要动，不存放具体的数据
    private HeroNode2 head = new HeroNode2(0,"","");

    /**
     * 遍历显示双链表中的元素
     */
    public void list(){
        if (head.next==null){
            System.out.println("链表为空");
            return;
        }
        //头结点不能动，因此需要一个辅助变量来遍历
        HeroNode2 temp=head;
        while (temp.next!=null){
            temp = temp.next;
            System.out.println(temp);
        }
    }

    /**
     * 按顺序将节点添加到链表
     * 1.先按顺序遍历链表，如找到应当的位置则将新节点插入，如未找到则打印提示
     * @param heroNode
     */
    public void addByOrder(HeroNode2 heroNode){
        HeroNode2 temp = head;
        boolean flag=false;//是否已存在该编号
        while (true){
            if (temp.next==null){
                break;
            }else if (temp.next.no>heroNode.no){
                //找到新节点应该插入的位置
                break;
            }else if (temp.next.no==heroNode.no){
                flag=true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            System.out.printf("当前编号%d已存在...",heroNode.no);
        }else {
            //插入数据
            heroNode.next = temp.next;
            //若temp不为最后的节点
            if (temp.next!=null){
                temp.next.pre=heroNode;
            }
            temp.next = heroNode;
            heroNode.pre=temp;

        }
    }

    /**
     * 添加节点到双向链表
     * 1. 找到当前链表的最后节点
     * 2. 将最后这个节点的next指向新的节点
     * 3. 将新节点的pre指向最后这个节点
     */
    public void add(HeroNode2 heroNode){
        //因为head节点不能动，因此我们需要一个辅助遍历temp
        HeroNode2 temp = head;
        //遍历链表，找到最后的节点，temp
        while (temp.next!=null){
            temp = temp.next;
        }
        //当while循环结束时，temp就指向了链表的最后
        temp.next = heroNode;
        //形成一个双向链表
        heroNode.pre=temp;
    }
    /**
     * 修改节点的信息，根据no编号来修改，所以no编号不能修改
     * @param heroNode
     */
    public void update(HeroNode2 heroNode){
        //判断是否为空
        if (head.next==null){
            System.out.println("链表为null....");
            return;
        }
        //不为空，则遍历找到需要修改的节点
        HeroNode2 temp = head;
        //是否找到修改的节点
        boolean flag = true;
        while (true){
            if (temp.next==null){
                flag=false;
                break;
            }else if (temp.next.no==heroNode.no){
                //找到该节点的前一个节点，跳出
                break;
            }
            temp = temp.next;
        }
        //找到该节点的前一个节点
        if (flag){
            temp.next.nickname = heroNode.nickname;
            temp.next.name = heroNode.name;
        }else {
            System.out.printf("未找到编号为%d的节点...",heroNode.no);
        }
    }

    /**
     * 删除节点
     * 思路：
     * 1.head不能动。需要辅助节点temp，直接找到待删除的节点  temp，将其删除即可
     * 2.  temp.pre.next=temp.next;
     *     temp.next.pre=temp.pre;
     * @param no
     */
    public void del(int no){
        HeroNode2 temp = head.next;
        //是否找到该节点
        boolean flag = true;
        while (true){
            if (temp==null){
                flag=false;
                break;
            }else if (temp.no==no){
                //找到该节点的前一个节点，跳出
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.pre.next=temp.next;
            //此处代码有问题，即若为最后一个节点，则此处会出现空指针异常
            //在此处加入判断，是否为最后一个节点...
            if(temp.next!=null){
                temp.next.pre=temp.pre;
            }
        }else {
            System.out.printf("未找到%d节点",no);
        }
    }

    public HeroNode2 getHead() {
        return head;
    }
}
/**
 * 定义HeroNode,每个HeroNode对象就是一个节点
 */
class HeroNode2{
    public int no;
    public String name;
    public String nickname;
    public HeroNode2 next;//指向后一个节点，默认为null
    public HeroNode2 pre;//指向前一个节点，默认为null
    //构造函数
    public HeroNode2(int no,String name,String nickname){
        this.no=no;
        this.name=name;
        this.nickname=nickname;
    }
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}
